import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-10-27
 * Time: 22:12
 */
public class MySort {

    /**
     * 挖坑法
     *
     * @param array 排序数组
     * @param left  左下标
     * @param right 右下标
     * @return 快排
     */
    private static int partition(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            array[i] = array[j];
            while (i < j && array[i] <= pivot) {
                i++;
            }
            array[j] = array[i];
        }
        array[i] = pivot;
        return i;
    }

    /**
     * @param array 排序数组
     * @param left  左下标
     * @param right 右下标
     * @return 快排
     */
    private static int partition1(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            while (i < j && array[i] <= pivot) {
                i++;
            }
            swap1(array, i, j);
        }
        swap1(array, i, left);
        return i;

    }

    /**
     *  交换元素
     * @param array 交换得素组
     * @param i   // 左下标中寻找得元素
     * @param j  // 右下标寻找得元素
     */
    private static void swap1(int[] array, int i, int j) {

    }

    /**
     * 快排思想
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        randomizedQuicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void randomizedQuicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuicksort(nums, l, pos - 1);
            randomizedQuicksort(nums, pos + 1, r);
        }
    }

    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition2(nums,l, r);
    }

    public int partition2(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
